﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinarySearchTree
{
    struct BinarySearchTree<T> :ICloneable,IEnumerable<T>
        where T:IComparable<T>
    {
        private TreeNode<T> node;
        private BinarySearchTree<T> leftSubtree;
        private BinarySearchTree<T> rightSubtree;

        private bool IsLeaf()
        {
            return this.node == null;
        }

        public void Add(T item)
        {
            TreeNode<T> newNode = new TreeNode<T>(item);
            if (node == null)
            {
                node = newNode;
                return;
            }
            if (node.CompareTo(newNode) < 0)
            {
                leftSubtree.Add(item);
            }
            else 
            {
                rightSubtree.Add(item);
            }
        }

        public T? Find(T item)
        {
            if (this.node.Value.CompareTo(item) == 0)
            {
                return this.node.Value;
            }
            if (node.Value.CompareTo(item) < 0)
            {
                if (leftSubtree.IsLeaf())
                {
                    return null;
                }
                else return leftSubtree.Find(item);
            }
            else
            {
                if (rightSubtree.IsLeaf())
                {
                    return null;
                }
                else return rightSubtree.Find(item);            
            }
        }
        
        public object Clone()
        {
            BinarySearchTree<T> result = new BinarySearchTree<T>();
            result.Add(this.node.Value);
            if (!leftSubtree.IsLeaf())
            {
                result.leftSubtree = (BinarySearchTree<T>)this.leftSubtree.Clone();
            }

            if (!rightSubtree.IsLeaf())
            {
                result.rightSubtree = (BinarySearchTree<T>)this.rightSubtree.Clone();
            }

            return result;
        }

        public IEnumerator<T> GetEnumerator()
        {
            yield return node.Value;

            if (!leftSubtree.IsLeaf())
            {
                foreach (T item in leftSubtree)
                {
                    yield return item;
                }
            }

            if (!rightSubtree.IsLeaf())
            {
                foreach (T item in rightSubtree)
                {
                    yield return item;
                }
            }

        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public static void Main()
        {
            BinarySearchTree<int> bstTest = new BinarySearchTree<int>();
            bstTest.Add(3);
            bstTest.Add(2);
            bstTest.Add(1);
            bstTest.Add(4);
            bstTest.Add(5);
            
        
        }
    }
}
